Skip to content

Results are limited to Maximum Independent Set v0.2.3

Product news
You are reading Maximum Independent Set v0.2.3, an older version of this documentation. Go to the latest version (v0.3.2)

Tutorial 1 - Using a Quantum Device to solve MIS

The MIS problem can be formulated as follows: given a graph G=(V,E)G=(V,E), an independent set is a subset of vertices S⊆VS\subseteq V such that no two vertices in SS are connected by an edge. The MIS problem then seeks to find the largest independent set in GG.

# Ignore warnings for this tutorial.
import logging
import os
import sys
logger = logging.getLogger()
logger.disabled = True
sys.stderr = open(os.devnull, 'w')
import networkx as nx
# Create a new networkx graph instance to be populated with DIMACS data.
graph = nx.Graph()
with open("./datasets/dimacs/a265032_1tc.32.txt", "r") as f:
for line in f:
if line.startswith("c"): # Comment line in DIMACS file.
continue
elif line.startswith("p"): # Problem definition, i.e. # nodes and edges.
_, _, num_nodes, num_edges = line.strip().split()
# Preset graph node labels as there might be isolated ones.
graph.add_nodes_from(range(1, int(num_nodes) + 1))
elif line.startswith("e"):
_, node1, node2 = line.strip().split()
graph.add_edge(int(node1), int(node2))
# Let's check what the graph looks like.
print(graph)
from mis import MISSolver, MISInstance, SolverConfig
# Define classical solver configuration
# Use a default configuration for the library.
# By default, the library uses a classical (non-quantum)
# heuristic solver.
config = SolverConfig()
# Create the MIS instance.
instance = MISInstance(graph)
# Run the solver and retrieve results.
solver = MISSolver(instance, config)
solutions = solver.solve()
# Display results
solutions[0].draw()
print("Solution nodes: ", solutions[0].nodes)
print("Solution frequency:", solutions[0].frequency)
print("Solution size:", solutions[0].size)
from mis import BackendConfig, BackendType
solver_config = SolverConfig(
# Use the QuTIP backend.
backend = BackendConfig(
backend = BackendType.QUTIP
),
# Perform up to 10 quantum measures.
max_iterations=10
)
# Run the solver
solver = MISSolver(instance, config)
solutions = solver.solve()
# Display results
print("MIS solution:", solutions[0].nodes)
print("Solution frequency:", solutions[0].frequency)
print("Solution size:", solutions[0].size)
solutions[0].draw()

This section illustrates the use of a QPU backend hosted on Pasqal's Cloud Platform. Provided that you are granted with credentials to access the platform, they should be passed to instantiate a RemoteQPUBackend.

# Replace with your username, project id and password on the Pasqal Cloud.
USERNAME="username"
PROJECT_ID="123"
PASSWORD=None
if PASSWORD is not None:
config = SolverConfig(
backend = BackendConfig(
backend=BackendType.REMOTE_QPU,
username=USERNAME,
project_id=PROJECT_ID,
password=PASSWORD
),
max_iterations=10
)
# Run the solver
solver = MISSolver(instance, config)
solutions = solver.solve()
# Display results
print("MIS solution:", solutions[0].nodes)
print("Solution cost:", solutions[0].frequency)
solutions[0].draw()